package algorithm.advance;
//Best Search Tree
public class BSTSYT {

	private static BSTSYT bst = new BSTSYT();
	public static BSTSYT getInstance(){
		return bst;
	}
	
	public ResultBST optimalBst(int[] p,int[] q,int n){
		ResultBST result = new ResultBST();
		int index = n + 1;
		int[][] e = new int[index + 1][index];
		int[][] w = new int[index + 1][index];
		int[][] root = new int[index][index];
		
		for(int i = 1;i<=index;i++){
			e[i][i-1] = q[i-1];
			w[i][i-1] = q[i-1];
		}
		for(int l=1;l<=n;l++){
			for(int i=1;l<=n-l+1;i++){
				int j = i + l - 1;
				e[i][j] = Integer.MAX_VALUE;
				w[i][j] = w[i][j-1] + p[j] + q[j];
				for(int r=i;r<=j;i++){   
			/* 替换"for(int r=i;r<=j;i++){ "  
			 * 
			 * "if(i == j){
			 * 	root[i][j] = i;
			 	* e[i,j] = p[i]+q[i-1]+q[i];
			 * }else{
			 *  	for(int r=root[i][j-1];r<=root[i+1][j];r++){"
			 */
					int t = e[i][r-1] + e[r+1][j] + w[i][j];
					if(t < e[i][j]){
						e[i][j] = t;
						root[i][j] = r;
					}
				}
			}
		}
		result.setE(e);
		result.setRoot(root);
		return result;
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

	 static class ResultBST{
		 private int[][] e;
		 private int[][] root;
		public int[][] getE() {
			return e;
		}
		public void setE(int[][] e) {
			this.e = e;
		}
		public int[][] getRoot() {
			return root;
		}
		public void setRoot(int[][] root) {
			this.root = root;
		}
	 }
}
